A system can be considered to be sparse when, in some basis, the system can be completely represented by only a few components out of a large set of possible components. For example, a sine wave would not appear to be sparse when sampled in the time domain; however, in the frequency domain, the sine wave corresponds to a single frequency value within a large space of possible frequency values. As another example, a vector of length N with one non-zero component can be considered to be sparse. As yet another example, a continuously sampled vector in time of a superposition of several sinusoids can be considered to be sparse in the frequency domain. Different criteria have been developed so as to distinguish between sparse and not-sparse signals in various contexts, and different methods have been developed so as to attempt to recover information from a sparse system.
For example, compressive sensing techniques have been developed for multiplexing signals when the expected inputs are sparse in some basis. As is known in the art, compressive sensing attempts to solve a linear set of equations of the form:y=A·x+δy  (1)where y is an M length measurement vector, x is an N length input vector to be recovered, M≤N, A is an M×N mixing matrix, and δy is the noise on the measurement. Let k represent the amount of information contained in N, then if k<M≤N, the signals can be reconstructed using known compressive sensing techniques. Compressive sensing techniques include, but are not limited to, l1-norm minimization such as described in Chen et al., “Atomic decomposition by basis pursuit,” SIAM Journal on Scientific Computing 20(1): 33-61 (1998), the entire contents of which are incorporated by reference herein; orthogonal matching pursuit such as described in Tropp et al., “Signal recovery from random measurements via orthogonal matching pursuit,” IEEE Trans. On Information Theory 53(12): 4655-4666 (2007), the entire contents of which are incorporated by reference herein; or a fast-iterative shrinking thresholding algorithm such as described in Beck et al., “A fast iterative shrinking-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences 2(1): 183-202 (2009), the entire contents of which are incorporated by reference herein. For further details regarding compressive sensing techniques, see Donoho, “Compressed sensing,” IEEE Trans. On Information Theory 52(4): 1289-1306 (2004), the entire contents of which are incorporated by reference herein.
By using compressive sensing techniques, a relatively large system can be reduced down in dimension, allowing for monitoring the system using significantly fewer channels than the number of signals output by that system. However, not every possible mixing matrix A will work. For example, a mixing matrix desirably samples the entire input space, does not have any degenerate rows (rows with all of the same values, in the same positions, as one another), and does not have any row that is degenerate with possible sparse inputs (rows do not match expected sparse input vectors). In practice, such features can be met by constructing pseudorandom mixing matrices, such as matrices having random values of 1 and −1, random Gaussian values, or sets of orthogonal vectors.
One difficulty in reconstructing a system comes from the sparsity constraint that can be expressed as:
                              M          ~          k                ⁢                                  ⁢        log        ⁢                  N          k                                    (        2        )            where M, N, and k are as defined above. Equation (2) expresses the approximate number of measurements needed to recover a sparse vector of a given size, and guides the choice in matrix. For further details regarding such a sparsity constraint, see Candès et al., “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE Trans. On Information Theory 52(12): 39 pages (2006), the entire contents of which are incorporated by reference herein.